package offer.day36;

public class No63MaxDiff {
    /*
     * 面试题63：股票的最大利润
     * 题目：假设把某股票的价格按照时间先后顺序存储在数组中，
     * 请问买卖该股票一次可能获得的最大利润是多少？
     * 例如：一只股票在某些时间节点的价格为{9，11，8，5，7，12，16，14}.
     * 如果能在价格为5的时候买入并在价格为16时卖出，则能收获的最大利润11
     *
     *
     * 思路：设定一个最小值和最大利润（差值），遍历数组，发现有比最小值小的则更新最小值
     * 若差值有比记录的最大利润大的 则更新最大利润
     * 时间复杂度O(n)
     * */
    public static void main(String[] args) {
        No63MaxDiff m = new No63MaxDiff();
        int[] values = {9,11,8,5,7,12,16,14};
        System.out.println("股票的最大利润："+m.MaxDiff(values));
    }

    private int MaxDiff(int[] values) {
        if(values==null||values.length==0) return -1;
        int min=values[0];
        int maxValue=values[1]-values[0];
        for(int i=2;i<values.length;i++){
            if(values[i-1]<min){
                min=values[i-1];
            }
            int curValue=values[i]-min;
            if(curValue>maxValue){
                maxValue=curValue;
            }
        }
        return maxValue;
    }
}
